package com.dycs.test;

import com.dimpt.unigw.token.TokenService;
import com.dycs.utils.SMSUtils;
import org.junit.jupiter.api.Test;

import java.io.*;
import java.security.KeyPair;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.sql.DataTruncation;
import java.util.*;
import java.util.stream.Collectors;

public class test {



//    @Test
//    public void test1() throws Exception {
//
////        char[][] board = new char[][]{
////                {'5','3','.','.','7','.','.','.','.'},
////                {'6','.','.','1','9','5','.','.','.'},
////                {'.','9','8','.','.','.','.','6','.'},
////                {'8','.','.','.','6','.','.','.','3'},
////                {'4','.','.','8','.','3','.','.','1'},
////                {'7','.','.','.','2','.','.','.','6'},
////                {'.','6','.','.','.','.','2','8','.'},
////                {'.','.','.','4','1','9','.','.','5'},
////                {'.','.','.','.','8','.','.','7','9'}
////        };
////        Algorithm.solveSudoku(board);
////        for (int i=0; i<9; i++) {
////            for (int j=0; j<9; j++) {
////                System.out.printf("  "+ board[i][j]);
////            }
////            System.out.println(" ");
////        }
//
////        System.out.println(Algorithm.combinationSum2(new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 30));
////        System.out.println(Algorithm.trap2(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
////        Integer[] ints = {3, 6, 7, 3, 1, 2, 4};
////        Algorithm.insertionSort(ints);
////        System.out.println(Arrays.toString(ints));
////        System.out.println(Algorithm.multiply("54","641"));
//
////        System.out.println(Algorithm.isMatch2("abcabczzzde","****decd"));
////        System.out.println(Algorithm.jump(new int[]{2,3,0,1,4}));
//
////        System.out.println(Algorithm.permuteUnique(new int[]{1,1,3}));
////        int[][] matrix = new int[][]{{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
////
////        for (int[] i : matrix) {
////            System.out.println(Arrays.toString(i));
////        }
////        Algorithm.rotate(matrix);
////        for (int[] i : matrix) {
////            System.out.println(Arrays.toString(i));
////        }
//        /*String username = "zhang", password = "123456", privateKey = "lsakhfof";
//        String Token1 = TokenService.generateToken(username,password), Token2 = TokenService.generateToken(username,privateKey);
//        System.out.println(Token1);
//        System.out.println(Token2);
//        System.out.println(TokenService.parseToken(Token1));
//        System.out.println(TokenService.parseToken(Token2));
//        KeyPair keyPair = TokenService.generateKeyPair();
//        String Token3 = TokenService.createToken(username, keyPair.getPrivate());
//        System.out.println(Token3);
//        System.out.println(TokenService.parseToken(Token3, keyPair.getPublic()));*/
////        String[] strs = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
////        System.out.println(Algorithm.groupAnagrams(strs));
////        System.out.println(Algorithm.myPow(2,10));
//        String Token1 = TokenService.generateTokenWithUsernameAndPassword("","123456");
//        System.out.println(Token1);
////        System.out.println("Token1: " + TokenService.decryptToken(Token1));
//        String Token2 = TokenService.generateTokenWithUserKeys("","wer");
//        System.out.println(Token2);
////        System.out.println("Token2: " + TokenService.decryptToken(Token2));
//    }
    @Test
    void test2() throws UnsupportedEncodingException, NoSuchAlgorithmException {
//        System.out.println(Algorithm.solveNQueens(5));
//        System.out.println(Algorithm.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
//        System.out.println(Algorithm.spiralOrder(new int[][]{{2,5},{8,4},{0,-1}}));
//        System.out.println(Algorithm.canJump(new int[]{3,2,1,0,4}));
//        for(int[] nums : Algorithm.merge(new  int[][]{{1,4},{0,4}})) {
//            System.out.printf("[ ");
//            for (int num : nums) {
//                System.out.printf(String.valueOf(num) + " ");
//            }
//            System.out.printf("]" + "\n");
//        }
//        for(int[] nums : Algorithm.generateMatrix(3)) {
//            System.out.printf("[ ");
//            for (int num : nums) {
//                System.out.printf(String.valueOf(num) + " ");
//            }
//            System.out.printf("]" + "\n");
//        }
//        System.out.println(Algorithm.getPermutation(9,8));
//        System.out.println(Algorithm.uniquePaths(3, 7));
//        System.out.println(Algorithm.isNumber("e9"));
//        System.out.println(Algorithm.addBinary("1010", "1011"));
//        System.out.println(Algorithm.fullJustify(new String[]{"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"}, 20));
//        String mobile = "149123456789";
//        String incompleteMobile;
//        boolean isMobile = true;
//        if (mobile.length() != 11) {
//            isMobile = false;
//        } else {
//            for (int i = 0; i < 11; i++) {
//                if (mobile.charAt(i) > '9' || mobile.charAt(i) < '0') {
//                    isMobile = false;
//                    break;
//                }
//            }
//        }
//        if (isMobile) {
//            incompleteMobile = mobile.substring(0, 3) + "****" + mobile.substring(7, 11);
//        } else {
//            incompleteMobile = "000****0000";
//        }
//        System.out.println(Algorithm.simplifyPath("/a//b////c/d//././/.."));
//        SMSUtils.sendMessage("阿里云短信测试", "SMS_154950909", "17838191731", "666666");
//        System.out.println(Algorithm.exist(new char[][]{{'A','B','C','E'}, {'S','F','C','S'},{'A','D','E','E'}}, "ABCB"));
//        System.out.println(Algorithm.maximalRectangle(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}));

//        System.out.println(Algorithm.subsetsWithDup(new int[]{1, 2, 2}));

        System.out.println(Algorithm.unName("101023"));
    }

    @Test
    void SerializableTest() {

        ListNode node = new ListNode(13,null);
        System.out.println(node);

        try {
            ObjectOutputStream outputStream = new ObjectOutputStream(new FileOutputStream("ListNode.txt"));
            outputStream.writeObject(new ListNode(13,null));
            outputStream.writeObject(new ListNode(14,null));
            outputStream.close();
            ObjectInputStream inputStream = new ObjectInputStream(new FileInputStream("ListNode.txt"));
            Object o = inputStream.readObject();
            System.out.println(o);
            inputStream.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    @Test
    void FinalTest() {
        FinalDemo finalDemo = new FinalDemo();
        System.out.println(finalDemo.id);
        System.out.println(finalDemo.user);

        FinalDemo finalDemo1 = new FinalDemo();
        System.out.println(finalDemo1.id);
        System.out.println(finalDemo1.user);
    }

    @Test
    void FileTest() throws IOException {

        File file = new File("文件夹");
        String[] list = file.list();
        for (String name : list) {
            System.out.println(name);
        }
        File[] files = file.listFiles();
        for (File path : files) {
            System.out.println(path.isFile());
            System.out.println(path.getPath());
        }

    }
}

class Algorithm {

    public static List<List<Integer>> list = new ArrayList<>();
    public static List<Integer> newList = new ArrayList<>();

    public static String longestCommonPrefix(String[] strs){

        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(strs[0]);
        for (int i=1; i<strs.length; i++){
            if (stringBuilder.length() == 0 || strs[i].length() == 0){
                return "";
            } else if (stringBuilder.length() > strs[i].length()) {
                stringBuilder.delete(strs[i].length(),stringBuilder.length());
            }
            for (int j=0; j<stringBuilder.length(); j++){
                if (stringBuilder.charAt(j) != strs[i].charAt(j)){
                    stringBuilder.delete(j,stringBuilder.length());
                    break;
                }
            }
        }
        return stringBuilder.toString();
    }

    public static List<List<Integer>> threeNum(int[] nums){

        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3){
            return list;
        }
        Arrays.sort(nums);
        int num1Index = 0, num2Index, num3Index;
        while (num1Index < nums.length - 2 && nums[num1Index] <= 0){
            if (nums[num1Index] + nums[num1Index+1] + nums[num1Index+2] > 0){
                break;
            }
            if (nums[num1Index] + nums[nums.length-1] + nums[nums.length-2] < 0){
                num1Index++;
                while (num1Index < nums.length - 2 && nums[num1Index] == nums[num1Index-1]){
                    num1Index++;
                }
                continue;
            }
            num2Index = num1Index + 1;
            num3Index = nums.length - 1;
            if (nums[num3Index] < 0){
                break;
            }
            while (num2Index < num3Index){
                if (nums[num1Index] + nums[num2Index] + nums[num3Index] == 0){
                    list.add(Arrays.asList(nums[num1Index],nums[num2Index],nums[num3Index]));
                    num2Index++;
                    while (num2Index < num3Index && nums[num2Index] == nums[num2Index-1]){
                        num2Index++;
                    }
                    num3Index--;
                    while (num2Index < num3Index && nums[num3Index] == nums[num3Index+1]){
                        num3Index--;
                    }
                }else if (nums[num1Index] + nums[num2Index] + nums[num3Index] < 0){
                    num2Index++;
                    while (num2Index < num3Index && nums[num2Index] == nums[num2Index-1]){
                        num2Index++;
                    }
                }else {
                    num3Index--;
                    while (num2Index < num3Index && nums[num3Index] == nums[num3Index+1]){
                        num3Index--;
                    }
                }
            }
            num1Index++;
            while (num1Index < nums.length - 2 && nums[num1Index] == nums[num1Index-1]){
                num1Index++;
            }
        }
        return list;
    }

    public static int threeSumClosest(int[] nums, int target){

        Arrays.sort(nums);
        int num1Index = 0, num2Index, num3Index, tarVal, limit = Integer.MAX_VALUE;
        while (num1Index < nums.length - 2){
            if (nums[num1Index] + nums[num1Index+1] + nums[num1Index+2] > target){
                if (Math.abs(target - limit) > Math.abs(target - (nums[num1Index] + nums[num1Index+1] + nums[num1Index+2]))){
                    limit = nums[num1Index] + nums[num1Index+1] + nums[num1Index+2];
                }
                break;
            }
            if (nums[num1Index] + nums[nums.length-1] + nums[nums.length-2] < target){
                if (Math.abs(target - limit) > Math.abs(target - (nums[num1Index] + nums[nums.length-1] + nums[nums.length-2]))){
                    limit = nums[num1Index] + nums[nums.length-1] + nums[nums.length-2];
                }
                num1Index++;
                while (num1Index < nums.length - 2 && nums[num1Index] == nums[num1Index-1]){
                    num1Index++;
                }
                continue;
            }
            num2Index = num1Index + 1;
            num3Index = nums.length - 1;
            tarVal = target - nums[num1Index];
            while (num2Index < num3Index){
                if (nums[num2Index] + nums[num3Index] == tarVal){
                    return target;
                } else if (nums[num2Index] + nums[num3Index] < tarVal) {
                    if (Math.abs(target - limit) > Math.abs(tarVal - nums[num2Index] - nums[num3Index])){
                        limit = nums[num1Index] + nums[num2Index] + nums[num3Index];
                    }
                    num2Index++;
                    while (num2Index < num3Index && nums[num2Index] == nums[num2Index-1]){
                        num2Index++;
                    }
                }else {
                    if (Math.abs(target - limit) > Math.abs(tarVal - nums[num2Index] - nums[num3Index])){
                        limit = nums[num1Index] + nums[num2Index] + nums[num3Index];
                    }
                    num3Index--;
                    while (num2Index < num3Index && nums[num3Index] == nums[num3Index+1]){
                        num3Index--;
                    }
                }
            }
            num1Index++;
            while (num1Index < nums.length - 2 && nums[num1Index] == nums[num1Index-1]){
                num1Index++;
            }
        }
        return limit;
    }

    public static List<String> letterCombinations(String digits) {

        List<String> list = new ArrayList<>();
        for (int i=0; i<digits.length(); i++){
            list = letterCombination(list,digits.charAt(i));
        }
        return list;
    }

    public static List<String> letterCombination(List<String> list, Character c) {
        Character[] characters;
        switch (c){
            case '2': characters = new Character[]{'a','b','c'};break;
            case '3': characters = new Character[]{'d','e','f'};break;
            case '4': characters = new Character[]{'g','h','i'};break;
            case '5': characters = new Character[]{'j','k','l'};break;
            case '6': characters = new Character[]{'m','n','o'};break;
            case '7': characters = new Character[]{'p','q','r','s'};break;
            case '8': characters = new Character[]{'t','u','v'};break;
            case '9': characters = new Character[]{'w','x','y','z'};break;
            default: characters = new Character[0];
        }
        if (characters.length == 0){
            return list;
        } else if (list.size() == 0){
            for (int i=0; i<characters.length; i++){
                list.add(characters[i].toString());
            }
            return list;
        } else {
            List<String> newList = new ArrayList<>();
            for (int i=0; i< characters.length; i++){
                Iterator<String> iterator = list.iterator();
                while (iterator.hasNext()){
                    newList.add(iterator.next() + characters[i]);
                }
            }
            return newList;
        }
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 4){
            return list;
        }
        Arrays.sort(nums);
        int num1Index = 0, num2Index, num3Index, num4Index, tarval, tarval2, flag;
        while (num1Index < nums.length - 3){
            if ((long) nums[num1Index] + nums[num1Index + 1] + nums[num1Index + 2] + nums[num1Index + 3] > target) {
                break;
            }
            if ((long) nums[num1Index] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                num1Index++;
                while (num1Index < nums.length - 3 && nums[num1Index] == nums[num1Index-1]){
                    num1Index++;
                }
                continue;
            }
            num2Index = num1Index + 1;
            tarval = nums[num1Index] + nums[num2Index];
            while (num2Index < nums.length -2){
                num3Index = num2Index + 1;
                num4Index = nums.length - 1;
                while (num3Index < num4Index){
                    tarval2 = nums[num3Index] + nums[num4Index];
                    if (tarval > 0 && tarval2 > 0 && tarval > Integer.MAX_VALUE - tarval2){
                        flag = 1;
                    } else if (tarval < 0 && tarval2 < 0 && tarval < Integer.MIN_VALUE - tarval2){
                        flag = 2;
                    } else {
                        flag = 0;
                    }
                    if (flag == 0 && tarval + tarval2 == target){
                        list.add(Arrays.asList(nums[num1Index],nums[num2Index],nums[num3Index],nums[num4Index]));
                        num3Index++;
                        while (num3Index < num4Index && nums[num3Index] == nums[num3Index-1]){
                            num3Index++;
                        }
                        num4Index--;
                        while (num3Index < num4Index && nums[num4Index] == nums[num4Index+1]){
                            num4Index--;
                        }
                    } else if ((flag == 0 && tarval + tarval2 < target) || flag == 2) {
                        num3Index++;
                        while (num3Index < num4Index && nums[num3Index] == nums[num3Index-1]){
                            num3Index++;
                        }
                    } else {
                        num4Index--;
                        while (num3Index < num4Index && nums[num4Index] == nums[num4Index+1]){
                            num4Index--;
                        }
                    }
                }
                num2Index++;
                while (num2Index < nums.length - 2 && nums[num2Index] == nums[num2Index-1]){
                    num2Index++;
                }
                tarval = nums[num1Index] + nums[num2Index];
            }
            num1Index++;
            while (num1Index < nums.length - 3 && nums[num1Index] == nums[num1Index-1]){
                num1Index++;
            }
        }
        return list;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode p = head;
        LinkedList<ListNode> listNodes = new LinkedList<>();
        while (p != null){
            listNodes.add(p);
            if (listNodes.size() > n+1){
                listNodes.removeFirst();
            }
            p = p.next;
        }
        if (listNodes.size() == n){
            if (n == 1){
                return null;
            }
            head = listNodes.get(1);
        }else if (listNodes.size() > n){
            listNodes.getFirst().next = listNodes.size() > 2 ? listNodes.get(2) : null;
        }
        return head;
    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<s.length(); i++){
            if (!stack.isEmpty()){
                Character c = stack.pop();
                if ((c == '(' && s.charAt(i) == ')') || (c == '{' && s.charAt(i) == '}') || (c == '[' && s.charAt(i) == ']')){
                    continue;
                }else {
                    stack.push(c);
                }
            }
            stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head,next;
        if (list1 == null || list2 == null) {
            return list1 != null ? list1 : list2;
        }else {
            if (list1.val < list2.val){
                head =  list1;
                list1 = list1.next;
            }else {
                head = list2;
                list2 = list2.next;
            }
            next = head;
        }
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                next.next = list1;
                list1 = list1.next;
            }else {
                next.next = list2;
                list2 = list2.next;
            }
            next = next.next;
        }
        next.next = list1 != null ? list1 : list2;
        return head;
    }

    public static List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        generateOne(list,stringBuilder,n,n);
        return list;
    }

    public static void generateOne(List<String> list,StringBuilder stringBuilder,int left,int right) {
        if (left == 0 && right == 0){
            list.add(stringBuilder.toString());
        }else {
            if (left > 0){
                stringBuilder.append('(');
                generateOne(list,stringBuilder,left-1,right);
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
            if (right > left){
                stringBuilder.append(')');
                generateOne(list,stringBuilder,left,right-1);
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {

        if (lists == null){
            return null;
        }

        int length = lists.length;
        int flag = 0, min, index;
        ListNode node = new ListNode(-1);
        ListNode beforeHead = node;

        for (int i=0; i<length; i++){
            if (lists[i] == null){
                flag++;
            }
        }

        while (flag < length){
            min = Integer.MAX_VALUE;
            index = 0;
            for (int i=0; i<length; i++){
                if (lists[i] == null){
                    continue;
                }
                if (lists[i].val < min){
                    min = lists[i].val;
                    index = i;
                }
            }
            node.next = lists[index];
            node = node.next;
            lists[index] = lists[index].next;
            if (lists[index] == null){
                flag++;
            }
        }

        return beforeHead.next;
    }

    public static ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null){
            return head;
        }
        ListNode p1 = head,p2 = head.next,p3;
        head = p2;
        while (true){
            if (p2.next != null && p2.next.next != null){
                p3 = p2.next;
                p1.next = p2.next.next;
                p2.next = p1;
                p1 = p3;
                p2 = p3.next;
            }else {
                p1.next = p2.next;
                p2.next = p1;
                break;
            }
        }
        return head;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode node1 = head, node2 = new ListNode(0), temp;
        head = node2;
        while (hasK(node1,k)){
            temp = reverseK(node1,k);
            node2.next = temp;
            node2 = node1;
            node1 = node1.next;
        }
        return head.next;
    }

    public static ListNode reverseK(ListNode head, int k){

        ListNode p1 = head,p2 = head.next,temp;
        for (int i=0; i<k-1; i++){
            temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }
        head.next = p2;
        return p1;
    }

    public static boolean hasK(ListNode head, int k){
        for (int i=0; i<k; i++){
            if (head == null){
                return false;
            }
            head = head.next;
        }
        return true;
    }

//    public static int removeDuplicates(int[] nums) {
//        int index=0;
//        for (int i=0; i<nums.length-1; i++){
//            if (nums[i] != nums[i+1]){
//                nums[index++] = nums[i];
//            }
//        }
//        nums[index++] = nums[nums.length-1];
//        return index;
//    }

    public static int removeElement(int[] nums, int val) {

        int index = 0;
        for (int i=0; i<nums.length; i++){
            if (nums[i] != val){
                nums[index++] = nums[i];
            }
        }
        return index;
    }

    public static int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    public static int doMaxHomework(int days, Integer[] works) {

        List<Integer> worksList = new ArrayList<>(Arrays.asList(works));

        return Math.max(doMax(days,worksList),doMax(days-1,worksList.subList(1, days)));
    }

    public static int doMax(int days, List<Integer> worksList) {

        if (days == 0) {
            return 0;
        }
        if (days == 1 || days == 2) {
            return worksList.get(0);
        }
        if (days == 3) {
            return worksList.get(0) + worksList.get(2);
        }
        return worksList.get(0) + Math.max(doMax(days-2,worksList.subList(2, days)),doMax(days-3,worksList.subList(3, days)));
    }

    public static int doMaxHomework2(int days, Integer[] works) {

        int[] max = new int[days+1];

        max[0] = 0;
        max[1] = works[0];
        max[2] = Math.max(works[1],works[0]);

        for (int i=2; i<days; i++) {
            max[i+1] = Math.max(works[i] + max[i-1],max[i]);
        }

        return max[days];
    }

    public static void nextPermutation(int[] nums) {

        int temp = -1;

        for (int i=nums.length-1; i>0; i--) {
            if (nums[i] > nums[i-1]) {
                for (int j=nums.length-1; j>=i; j--) {
                    if (nums[j] > nums[i-1]) {
                        temp = nums[j];
                        nums[j] = nums[i-1];
                        nums[i-1] = temp;
                        for (int k=0; k<(nums.length-i)/2; k++) {
                            temp = nums[k+i];
                            nums[k+i] = nums[nums.length-1-k];
                            nums[nums.length-1-k] = temp;
                        }
                        break;
                    }
                }
                break;
            }
        }

        if (temp == -1) {
            for (int i=0; i<nums.length/2; i++) {
                temp = nums[i];
                nums[i] = nums[nums.length-1-i];
                nums[nums.length-1-i] = temp;
            }
        }

    }

    public static int longestValidParentheses(String s) {

        int left = 0, right = 0, max = 0;

        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == ')') {
                right++;
                if (left == right) {
                    max = Math.max(max,left);
                }
                if (left < right) {
                    left = 0;
                    right = 0;
                }
                continue;
            }
            left++;
        }
        left = 0;
        right = 0;
        for (int i=s.length()-1; i>=0; i--) {
            if (s.charAt(i) == '(') {
                right++;
                if (left == right) {
                    max = Math.max(max,left);
                }
                if (left < right) {
                    left = 0;
                    right = 0;
                }
                continue;
            }
            left++;
        }

        return max * 2;
    }

//    public static int search(int[] nums, int target) {
//
//        if (nums[0] > target && (nums[nums.length-1] < target || nums[0] < nums[nums.length-1])) {
//            return -1;
//        }
//
//        int left = 0, right = nums.length-1, mid;
//
//        if (nums[0] <= target) {
//            do {
//                mid = (left + right)/2;
//                if (nums[mid] < nums[0]) {
//                    right = mid - 1;
//                    continue;
//                }
//                if (nums[mid] == target) {
//                    return mid;
//                } else if (nums[mid] > target) {
//                    right = mid - 1;
//                } else {
//                    left = mid + 1;
//                }
//            }while (left <= right);
//        } else {
//            do {
//                mid = (left + right)/2;
//                if (nums[mid] > nums[nums.length-1]) {
//                    left = mid + 1;
//                    continue;
//                }
//                if (nums[mid] == target) {
//                    return mid;
//                } else if (nums[mid] > target) {
//                    right = mid - 1;
//                } else {
//                    left = mid + 1;
//                }
//            }while (left <= right);
//        }
//        return -1;
//    }

    public static int[] searchRange(int[] nums, int target) {

        int[] range = new int[2];
        range[0] = range[1] = -1;
        find(nums,0, nums.length-1,target,range);
        return range;
    }

    public static void find(int[] nums, int start, int end, int target, int[] range) {

        if (start > end) {
            return;
        }

        int mid;

        do {
            mid = (start + end)/2;
            if (nums[mid] == target) {
                if (range[0] == -1) {
                    range[0] = mid;
                } else {
                    range[0] = Math.min(range[0],mid);
                }
                range[1] = Math.max(range[1],mid);
                if (start != end) {
                    find(nums,start,mid-1,target,range);
                    find(nums,mid+1,end,target,range);
                }
            }
            if (nums[mid] < target) {
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }while (start <= end);
    }

    public static int[] searchRange2(int[] nums, int target) {

        int[] range = new int[2];
        range[0] = find2(nums,target,true);
        range[1] = find2(nums,target,false) - 1;
        if (range[0] > range[1]) {
            range[0] = range[1] = -1;
        }
        return range;
    }

    public static int find2(int[] nums, int target, boolean flag) {

        int left = 0, right = nums.length - 1, mid, ans = nums.length;

        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] > target || (flag && nums[mid] == target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }

    public static int searchInsert(int[] nums, int target) {

        int left = 0, right = nums.length - 1, mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    public static boolean isValidSudoku(char[][] board) {

        int[][] checkRow = new int[9][9], checkColumn = new int[9][9], checkCheck = new int[9][9];
        int temp,k;

        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] != '.') {
                    temp = board[i][j] - '1';
                    k = i/3*3 + j/3;
                    if (checkRow[i][temp] == 1 || checkColumn[j][temp] == 1 || checkCheck[k][temp] == 1) {
                        return false;
                    }
                    checkRow[i][temp]++;
                    checkColumn[j][temp]++;
                    checkCheck[k][temp]++;
                }
            }
        }

        return true;
    }

    public static void solveSudoku(char[][] board) {

//        初始化
        int[][] checkRow = new int[9][9], checkColumn = new int[9][9], checkCheck = new int[9][9];
        int temp,k;

        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] != '.') {
                    temp = board[i][j] - '1';
                    k = i/3*3 + j/3;
                    checkRow[i][temp]++;
                    checkColumn[j][temp]++;
                    checkCheck[k][temp]++;
                }
            }
        }

        isAble(checkRow,checkColumn,checkCheck,board);

    }

    public static boolean isAble(int[][] checkRow, int[][] checkColumn, int[][] checkCheck, char[][] board) {

        int k, temp;
        boolean flag;
        List<Integer> list = new ArrayList<>();

        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] == '.') {
                    k = i/3*3 + j/3;
                    for (int index=0; index<9; index++) {
                        if (checkRow[i][index] == 0 && checkColumn[j][index] == 0 && checkCheck[k][index] == 0) {
                            list.add(index);
                        }
                    }
                    if (list.size() == 0) {
                        return false;
                    }
                    for (int step=0; step<list.size(); step++) {
                        temp = list.get(step);
                        checkRow[i][temp]++;
                        checkColumn[j][temp]++;
                        checkCheck[k][temp]++;
                        board[i][j] = (char) (49 + temp);
                        flag = isAble(checkRow,checkColumn,checkCheck,board);
                        if (!flag) {
                            checkRow[i][temp]--;
                            checkColumn[j][temp]--;
                            checkCheck[k][temp]--;
                            board[i][j] = '.';
                        } else {
                            return true;
                        }
                    }
                    if (board[i][j] == '.') {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    public static String countAndSay(int n) {

        StringBuilder stringBuilder = new StringBuilder("1");
        int count, length;
        char c;

        for (int i=1; i<n; i++) {
            count = 1;
            c = stringBuilder.charAt(0);
            length = stringBuilder.length();
            for (int j=1; j<length; j++) {
                if (stringBuilder.charAt(j-1) == stringBuilder.charAt(j)) {
                    count++;
                } else {
                    stringBuilder.append((char) ('0' + count)).append(c);
                    count = 1;
                    c = stringBuilder.charAt(j);
                }
            }
            stringBuilder.append((char) ('0' + count)).append(c);
            stringBuilder.delete(0, length);
        }

        return stringBuilder.toString();
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> list = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();

        Arrays.sort(candidates);
        combinationTarget(candidates, target, list, combination, 0);

        return list;
    }

    public static void combinationTarget(int[] candidates, int target, List<List<Integer>> list, List<Integer> combination, int index) {

        int length = candidates.length;
        while (index < length && candidates[index] <= target) {
            if (candidates[index] == target) {
                combination.add(candidates[index]);
                list.add(new ArrayList<>(combination));
                combination.remove(combination.size() - 1);
            } else {
                combination.add(candidates[index]);
                combinationTarget(candidates, target - candidates[index], list, combination, index);
                combination.remove(combination.size() - 1);
            }
            index++;
        }
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Set<List<Integer>> list = new HashSet<>();
        List<Integer> combination = new ArrayList<>();

        Arrays.sort(candidates);
        combinationTarget2(candidates, target, list, combination, 0);

        return new ArrayList<>(list);
    }

    public static void combinationTarget2(int[] candidates, int target, Set<List<Integer>> list, List<Integer> combination, int index) {

        int length = candidates.length;

        while (index < length && candidates[index] <= target) {
            if (candidates[index] == target) {
                combination.add(candidates[index]);
                list.add(new ArrayList<>(combination));
                combination.remove(combination.size() - 1);
            } else {
                combination.add(candidates[index]);
                combinationTarget2(candidates, target - candidates[index], list, combination, index + 1);
                combination.remove(combination.size() - 1);
            }
            index++;
        }
    }

    public static int firstMissingPositive(int[] nums) {

        int n = nums.length, temp;

        for (int i=0; i<n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        for (int i=0; i<n; i++) {
            if (nums[i] != i + 1) {
                return i+1;
            }
        }

        return n+1;
    }

    public static int trap(int[] height) {

        int high = 0, index1 = 0, index2 = height.length - 1, capacity = 0;

        for (int i=index1; i<height.length; i++) {
            if (high <= height[i]) {
                for (int j = index1 + 1; j < i; j++) {
                    capacity += high - height[j];
                }
                high = height[i];
                index1 = i;
            }
        }
        high = 0;
        for (int i=index2; i>=index1; i--) {
            if (high <= height[i]) {
                for (int j=i+1; j<index2; j++) {
                    capacity += high - height[j];
                }
                high = height[i];
                index2 = i;
            }
        }
        return capacity;
    }

    public static int trap2(int[] height) {

        int left_index = 0, right_index = height.length - 1, left_max = height[left_index], right_max = height[right_index], capacity = 0;

        while (left_index < right_index) {

            if (left_max < right_max) {

                left_index++;

                if (height[left_index] > left_max) {
                    left_max = height[left_index];

                }
                if (height[left_index] < left_max) {
                    capacity += left_max - height[left_index];
                }

            } else {

                right_index--;

                if (height[right_index] > right_max) {
                    right_max = height[right_index];
                }
                if (height[right_index] < right_max) {
                    capacity += right_max - height[right_index];
                }

            }
        }

        return capacity;

    }

    public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a) {

        int j;

        for (int p = 1; p < a.length; p++) {
            AnyType tmp = a[p];
            for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    public static String multiply(String num1, String num2) {

        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        StringBuilder sum = new StringBuilder("0"), count = new StringBuilder(num2), add = new StringBuilder(num1), pow = new StringBuilder("1");
        int[] record = new int[670];
        int length, flag;

        while (count.length() > 1 || (count.length() == 1 && count.charAt(0) != '0')) {
            flag = 0;
            pow.delete(0,pow.length());
            pow.append('1');
            while (compareString(count,pow)) {
                record[flag]++;
                subtractionString(count,pow.toString());
                AddString(pow,pow);
                flag++;
            }
        }

        for (int i=0; i<record.length; i++) {

            while (record[i] != 0) {
                AddString(sum,add);
                record[i]--;
            }
            AddString(add,add);
        }

        return sum.toString();
    }

    public static void AddString(StringBuilder sum, StringBuilder add) {

        int carry = 0, length = Math.min(sum.length(),add.length());

        for (int i=1; i<=length; i++) {
            carry = carry + sum.charAt(sum.length() - i) + add.charAt(add.length() - i) - '0' - '0';
            if (carry < 10) {
                sum.setCharAt(sum.length() - i, (char) (carry + '0'));
                carry = 0;
            } else {
                sum.setCharAt(sum.length() - i, (char) (carry + '0' - 10));
                carry = 1;
            }
        }
        for (int i=length+1; i<=sum.length(); i++) {
            carry = carry + sum.charAt(sum.length() - i) - '0';
            if (carry < 10) {
                sum.setCharAt(sum.length() - i, (char) (carry + '0'));
                carry = 0;
            } else {
                sum.setCharAt(sum.length() - i, (char) (carry + '0' - 10));
                carry = 1;
            }
        }
        for (int i=length+1; i<=add.length(); i++) {
            carry = carry + add.charAt(add.length() - i) - '0';
            if (carry < 10) {
                sum.insert(0,(char) (carry + '0'));
                carry = 0;
            } else {
                sum.insert(0,(char) (carry + '0' - 10));
                carry = 1;
            }
        }
        if (carry > 0) {
            sum.insert(0,(char) (carry + '0'));
        }
    }

    public static boolean compareString(StringBuilder count, StringBuilder cmp) {

        if (count.length() > cmp.length()) {
            return true;
        }
        if (count.length() < cmp.length()) {
            return false;
        }
        for (int i=0; i<count.length(); i++) {
            if (count.charAt(i) < cmp.charAt(i)) {
                return false;
            }
            if (count.charAt(i) > cmp.charAt(i)) {
                return true;
            }
        }

        return true;
    }

    public static void subtractionString(StringBuilder count, String cmp) {

        int length = cmp.length(), carry = 0;

        for (int i=1; i<=length; i++) {
            carry = carry + count.charAt(count.length() - i) - cmp.charAt(cmp.length() - i);
            if (carry < 0) {
                count.setCharAt(count.length() - i,(char) (carry + 10 + '0'));
                carry = -1;
            } else {
                count.setCharAt(count.length() - i,(char) (carry + '0'));
                carry = 0;
            }
        }
        while (carry < 0) {
            length++;
            carry = carry + count.charAt(count.length() - length) - '0';
            if (carry < 0) {
                count.setCharAt(count.length() - length,(char) (carry + 10 + '0'));
                carry = -1;
            } else {
                count.setCharAt(count.length() - length,(char) (carry + '0'));
                carry = 0;
            }
        }
        while (count.length() > 1) {
            if (count.charAt(0) != '0') {
                break;
            }
            count.deleteCharAt(0);
        }
    }

    public static boolean isMatch(String s, String p) {

        if (s.length() == 0 && p.length() == 0) {
            return true;
        }
        if (s.length() != 0 && p.length() == 0) {
            return false;
        }

        int length1 = s.length(), length2 = p.length();
        boolean[][] match = new boolean[length1 + 1][length2 + 1];

        match[0][0] = true;

        for (int i = 0; i < length2; i++) {
            if (p.charAt(i) == '*') {
                match[0][i+1] = match[0][i];
            }
            for (int j = 0; j < length1; j++) {
                if (p.charAt(i) == '*') {
                    match[j+1][i+1] = match[j+1][i] || match[j][i+1];
                    continue;
                }
                if (p.charAt(i) == '?') {
                    match[j+1][i+1] = match[j][i];
                } else {
                    match[j+1][i+1] = match[j][i] && p.charAt(i) == s.charAt(j);
                }
            }
        }

        return match[length1][length2];
    }

    public static boolean isMatch2(String s, String p) {

        int sRight = s.length(), pRight = p.length();
        while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
            if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
                --sRight;
                --pRight;
            } else {
                return false;
            }
        }

        if (pRight == 0) {
            return sRight == 0;
        }

        int sIndex = 0, pIndex = 0;
        int sRecord = -1, pRecord = -1;

        while (sIndex < sRight && pIndex < pRight) {
            if (p.charAt(pIndex) == '*') {
                ++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;
            } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
                ++sIndex;
                ++pIndex;
            } else if (sRecord != -1 && sRecord + 1 < sRight) {
                ++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;
            } else {
                return false;
            }
        }

        return allStars(p, pIndex, pRight);
    }

    public static boolean allStars(String str, int left, int right) {
        for (int i = left; i < right; ++i) {
            if (str.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }

    public static boolean charMatch(char u, char v) {
        return u == v || v == '?';
    }

    public static int jump(int[] nums) {

        int index = 0, n = nums.length - 1, max = 0, maxIndex = 0, step = 0;

        while (index < n) {
            step++;
            if (index + nums[index] >= n) {
                break;
            }
            for (int i = 1; i <= nums[index] && i < n - index; i++) {
                if (nums[index + i] > --max) {
                    max = nums[index + i];
                    maxIndex = i;
                }
            }
            index += maxIndex;
        }

        return step;
    }

    public static List<List<Integer>> permute(int[] nums) {

        permute2(nums);

        return list;

    }

    public static void permute2(int[] nums) {

        if (nums.length == 1) {
            newList.add(nums[0]);
            list.add(new ArrayList<>(newList));
            newList.remove(newList.size() - 1);
        } else {
            for (int i = 0; i < nums.length; i++) {
                newList.add(nums[i]);
                int[] newNums = new int[nums.length - 1];
                for (int j = 0; j < i; j++) {
                    newNums[j] = nums[j];
                }
                for (int j = i + 1; j < nums.length; j++) {
                    newNums[j - 1] = nums[j];
                }
                permute(newNums);
                newList.remove(newList.size() - 1);
            }
        }

    }

    public static List<List<Integer>> permuteUnique(int[] nums) {

        Arrays.sort(nums);

        permuteUnique2(nums);

        return list;

    }

    public static void permuteUnique2(int[] nums) {

        if (nums.length == 1) {
            newList.add(nums[0]);
            list.add(new ArrayList<>(newList));
            newList.remove(newList.size() - 1);
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (i != nums.length - 1 && nums[i] == nums[i + 1]) {
                    continue;
                }
                newList.add(nums[i]);
                int[] newNums = new int[nums.length - 1];
                for (int j = 0; j < i; j++) {
                    newNums[j] = nums[j];
                }
                for (int j = i + 1; j < nums.length; j++) {
                    newNums[j - 1] = nums[j];
                }
                permuteUnique2(newNums);
                newList.remove(newList.size() - 1);
            }
        }

    }

    public static void rotate(int[][] matrix) {

        int length = matrix.length;

        if (length == 1) {
            return;
        }

        int shift = length - 1, temp;

        for (int i = 0; i < length / 2; i++) {
            for (int j = 0; j < shift; j++) {
                temp = matrix[i][j + i];
                matrix[i][j + i] = matrix[length - i - 1 - j][i];
                matrix[length - i - 1 - j][i] = matrix[length - i - 1][length - i - 1 - j];
                matrix[length - i - 1][length - i - 1 - j] = matrix[i + j][length - i - 1];
                matrix[i + j][length - i - 1] = temp;
            }
            shift -= 2;
        }


    }

    public static List<List<String>> groupAnagrams(String[] strs) {

        int length = strs.length, index = 0;
        Map<String, Integer> map = new HashMap<>();
        List<List<String>> list = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            String temp = sort(strs[i]);
            if (map.containsKey(temp)) {
                list.get(map.get(temp)).add(strs[i]);
            } else {
                map.put(temp, index);
                list.add(new ArrayList<>());
                list.get(index++).add(strs[i]);
            }
        }

        return list;
    }

    public static String sort(String str) {

        byte[] bytes = str.getBytes();

        Arrays.sort(bytes);

        return new String(bytes);
    }

    public static double myPow(double x, int n) {

        if (n == 0) {
            return 1;
        }

        int count = n, index = 0;
        int[] num = new int[31];
        double sum = 1, pow = x;
        boolean flag = n < 0;

        while (count != 0) {
            num[index++] = count % 2;
            count /= 2;
        }

        if (flag) {
            for (int i = 0; i < 31; i++) {
                if (num[i] != 0) {
                    sum /= pow;
                }
                pow *= pow;
            }
        } else {
            for (int i = 0; i < 31; i++) {
                if (num[i] != 0) {
                    sum *= pow;
                }
                pow *= pow;
            }
        }

        return sum;
    }

    public static List<List<String>> solveNQueens(int n) {

        List<List<String>> lists = new ArrayList<>();
        int[][] checkerboard = new int[n][n];

        isValid(checkerboard,0,n,lists);

        return lists;

    }

    public static void isValid(int[][] checkerboard, int next, int n, List<List<String>> lists) {

        if (next == n) {
            StringBuilder row = new StringBuilder();
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (checkerboard[i][j] == 0) {
                        row.append('.');
                    } else {
                        row.append('Q');
                    }
                }
                list.add(row.toString());
                row.delete(0,n);
            }
            lists.add(list);
        } else {
            boolean flag;
            for (int i = 0; i < n; i++) {
                flag = true;
                for (int j = 0; j < next; j++) {
                    if (checkerboard[j][i] != 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    for (int j = i - 1, k = next - 1; j >= 0 && k >= 0; j--, k--) {
                        if (checkerboard[k][j] != 0) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        for (int j = i + 1, k = next - 1; j < n && k >= 0; j++, k--) {
                            if (checkerboard[k][j] != 0) {
                                flag = false;
                                break;
                            }
                        }
                    }
                }
                if (flag) {
                    checkerboard[next++][i] = 1;
                    isValid(checkerboard,next,n,lists);
                    checkerboard[--next][i] = 0;
                }
            }
        }
    }

    public static int maxSubArray(int[] nums) {

        int max = Integer.MIN_VALUE, sum = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                if (sum == 0) {
                    max = Math.max(max, nums[i]);
                } else {
                    max = Math.max(max, sum);
                    sum += nums[i];
                    sum = Math.max(0, sum);
                }
            } else {
                sum += nums[i];
            }
        }

        if (sum > 0) {
            max = Math.max(max, sum);
        }

        return max;
    }

    public static List<Integer> spiralOrder(int[][] matrix) {

        int length = matrix[0].length, width = matrix.length, circle = 0, count = Math.min(length, width) / 2, flag = Math.min(length, width) % 2;
        List<Integer> list = new ArrayList<>();

        while (circle < count) {
            for (int j = circle; j < length - 1 - circle; j++) {
                list.add(matrix[circle][j]);
            }
            for (int i = circle; i < width - 1 - circle; i++) {
                list.add(matrix[i][length - 1 - circle]);
            }
            for (int j = length - 1 - circle; j > circle; j--) {
                list.add(matrix[width - 1 - circle][j]);
            }
            for (int i = width - 1 - circle; i > circle; i--) {
                list.add(matrix[i][circle]);
            }
            circle++;
        }

        if (flag == 1) {
            if (length > width) {
                for (int j = circle; j < length - circle; j++) {
                    list.add(matrix[circle][j]);
                }
            } else {
                for (int i = circle; i < width - circle; i++) {
                    list.add(matrix[i][length - 1 - circle]);
                }
            }
        }


        return list;
    }

    public static boolean canJump(int[] nums) {

        int maxJump = 0, length = nums.length;

        for (int i = 0; i < length; i++) {

            if (i <= maxJump) {
                maxJump = Math.max(maxJump, nums[i] + i);
            } else {
                return false;
            }

            if (maxJump >= length - 1) {
                return true;
            }
        }

        return true;
    }

    public static int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        List<int[]> list = new ArrayList<>();
        int[] union = new int[]{intervals[0][0],intervals[0][1]};

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= union[1]) {
                union[1] = Math.max(union[1],intervals[i][1]);
            } else {
                list.add(new int[]{union[0],union[1]});
                union[0] = intervals[i][0];
                union[1] = intervals[i][1];
            }
        }

        list.add(union);

        return list.toArray(new int[0][]);
    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {

        List<int[]> list = new ArrayList<>();
        int length = intervals.length;
        boolean flag = true;

        if (length == 0) {
            list.add(newInterval);
            return list.toArray(new int[0][]);
        }

        for (int i = 0; i < length; i++) {
            if (flag) {
                if (newInterval[0] <= intervals[i][0]) {
                    if (newInterval[1] < intervals[i][0]) {
                        list.add(newInterval);
                        list.add(intervals[i]);
                        flag = false;
                    } else {
                        if (newInterval[1] <= intervals[i][1]) {
                            intervals[i][0] = newInterval[0];
                            list.add(intervals[i]);
                            flag = false;
                        } else {
                            if (i == length - 1 || newInterval[1] < intervals[i + 1][0]) {
                                list.add(newInterval);
                                flag = false;
                            }
                        }
                    }

                } else {
                    if (newInterval[0] > intervals[i][1]) {
                        list.add(intervals[i]);
                    } else {
                        if (newInterval[1] <= intervals[i][1]) {
                            list.add(intervals[i]);
                            flag = false;
                        } else {
                            newInterval[0] = intervals[i][0];
                        }
                    }
                }
            } else {
                list.add(intervals[i]);
            }
        }

        if (flag) {
            list.add(newInterval);
        }

        return list.toArray(new int[0][]);
    }

    public static int lengthOfLastWord(String s) {

        int n = s.length() - 1, length = 0;

        for (int i = n; i >= 0; i--) {
            if (s.charAt(i) != ' ') {
                n = i;
                break;
            }
        }

        for (int i = n; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                break;
            }
            length++;
        }

        return length;
    }

    public static int[][] generateMatrix(int n) {

        int[][] matrix = new int[n][n];
        int[][] rules = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int i = 0, j = -1, k = 1, rule = 0;

        while (k <= n * n){
            i += rules[rule][0];
            j += rules[rule][1];
            if (i < n && i >= 0 && j >= 0 && j < n && matrix[i][j] == 0) {
                matrix[i][j] = k++;
            } else {
                i -= rules[rule][0];
                j -= rules[rule][1];
                rule = (rule + 1) % 4;
            }
        }

        return matrix;
    }

    public static String getPermutation(int n, int k) {

        int count = 1, index = 0, length = n - 1, sum = k - 1;
        int[] num = new int[n];
        StringBuilder ans = new StringBuilder();

        for (int i = length; i > 1; i--) {
            count *= i;
        }

        while (length > 0) {
            index = sum / count;
            sum = sum % count;
            count /= length;
            length--;
            for (int i = 0; i < n; i++) {
                if (num[i] == 0) {
                    index--;
                    if (index < 0) {
                        ans.append(i + 1);
                        num[i] = -1;
                        break;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (num[i] == 0) {
                ans.append(i + 1);
                break;
            }
        }
        return ans.toString();
    }

    public static ListNode rotateRight(ListNode head, int k) {

        if (head == null || head.next == null || k == 0) {
            return head;
        }

        int length = 0, target;
        ListNode p = new ListNode(), end;

        p.next = head;

        while (p.next != null) {
            p = p.next;
            length++;
        }

        target = length - k % length;

        if (target != length) {
            p.next = head;
            while (target > 0) {
                p = p.next;
                target--;
            }
            head = p.next;
            p.next = null;
        }

        return head;
    }
//    public static int uniquePaths(int m, int n) {
//
//        int step = m + n - 2, count = Math.min(m, n) - 1, ans = 1;
//
//        for (int i = 1; i <= count; i++) {
//            ans = ans * (step - count + i) / i;
//        }
//
//        return ans;
//    }
    public static int uniquePaths(int m, int n) {

        int[][] paths = new int[m + 1][n + 1];
        int circle = Math.min(m, n), count = 0;

        paths[0][1] = 1;

        while (++count <= circle) {
            for (int i = count; i <= m; i++) {
                paths[i][count] = paths[i - 1][count] + paths[i][count - 1];
            }
            for (int i = count; i <= n; i++) {
                paths[count][i] = paths[count - 1][i] + paths[count][i - 1];
            }
        }

        return paths[m][n];
    }
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length, n = obstacleGrid[0].length, circle = Math.min(m, n), count = 0;
        int[][] paths = new int[m + 1][n + 1];

        paths[0][1] = 1;

        while (++count <= circle) {
            for (int i = count; i <= m; i++) {
                if (obstacleGrid[i - 1][count - 1] == 1) {
                    paths[i][count] = 0;
                } else {
                    paths[i][count] = paths[i - 1][count] + paths[i][count - 1];
                }
            }
            for (int i = count; i <= n; i++) {
                if (obstacleGrid[count - 1][i - 1] == 1) {
                    paths[count][i] = 0;
                } else {
                    paths[count][i] = paths[count - 1][i] + paths[count][i - 1];
                }
            }
        }

        return paths[m][n];
    }
    public static int minPathSum(int[][] grid) {

        int m = grid.length, n = grid[0].length;
        int[] pathSum = new int[n];

        pathSum[0] = grid[0][0];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    pathSum[j] = Math.min(pathSum[j - 1], pathSum[j]) + grid[i][j];
                    continue;
                }
                if (i > 0) {
                    pathSum[j] += grid[i][j];
                    continue;
                }
                if (j > 0) {
                    pathSum[j] = pathSum[j - 1] + grid[i][j];
                }
            }
        }

        return pathSum[n - 1];
    }
    public static boolean isNumber(String s) {

        boolean flag = true;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '+' || s.charAt(i) == '-') {
                if ((i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E') && i + 1 < s.length() && (s.charAt(i + 1) == '.' || (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9'))) {
                    continue;
                } else {
                    return false;
                }
            }
            if (s.charAt(i) == 'e' || s.charAt(i) == 'E') {

                if (i > 0 && (s.charAt(i - 1) == '.' || (s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9')) && i + 1 < s.length() && (((s.charAt(i + 1) == '+' || s.charAt(i + 1) == '-') && i + 2 < s.length()) || ((s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9')))) {
                    for (int j = i + 2; j < s.length(); j++) {
                        if (s.charAt(j) < '0' || s.charAt(j) > '9') {
                            return false;
                        }
                    }
                    return true;
                } else {
                    return false;
                }
            }
            if (s.charAt(i) == '.' && flag) {
                flag = false;
                if (i == 0 && i + 1 < s.length() && (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9')) {
                    continue;
                }
                if (i > 0 && i + 1 == s.length() && (s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9')) {
                    continue;
                }
                if (i > 0 && i + 1 < s.length() && ((s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9') || (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9'))) {
                    continue;
                }
                return false;
            }
            if (s.charAt(i) < '0' || s.charAt(i) > '9') {
                return false;
            }
        }

        return true;
    }
    public static int[] plusOne(int[] digits) {

        int length = digits.length;
        boolean isCarry = true;
        int[] ans;

        for (int i = length - 1; i >= 0 && isCarry; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i]++;
                isCarry = false;
            }
        }

        if (isCarry) {
            ans = new int[length + 1];
            ans[0] = 1;
            while (length > 0) {
                ans[length--] = 0;
            }
        } else {
            ans = digits;
        }

        return ans;
    }
    public static String addBinary(String a, String b) {

        int n = a.length(), m = b.length();
        boolean isCarry = false;
        StringBuilder sumBinary = new StringBuilder();

        while (n > 0 && m > 0) {
            n--;
            m--;
            boolean b1 = a.charAt(n) == '1' && b.charAt(m) == '1';
            boolean b2 = a.charAt(n) == '1' || b.charAt(m) == '1';
            if (isCarry) {
                if (b1) {
                    sumBinary.append('1');
                } else if (b2) {
                    sumBinary.append('0');
                } else {
                    sumBinary.append('1');
                    isCarry = false;
                }
            } else {
                if (b1) {
                    sumBinary.append('0');
                    isCarry = true;
                } else if (b2) {
                    sumBinary.append('1');
                } else {
                    sumBinary.append('0');
                }
            }
        }

        while (n > 0) {
            if (isCarry) {
                if (a.charAt(--n) == '1') {
                    sumBinary.append('0');
                } else {
                    sumBinary.append('1');
                    isCarry = false;
                }
            } else {
                sumBinary.append(a.charAt(--n));
            }
        }

        while (m > 0) {
            if (isCarry) {
                if (b.charAt(--m) == '1') {
                    sumBinary.append('0');
                } else {
                    sumBinary.append('1');
                    isCarry = false;
                }
            } else {
                sumBinary.append(b.charAt(--m));
            }
        }

        if (isCarry) {
            sumBinary.append('1');
        }

        return sumBinary.reverse().toString();
    }
    public static int mySqrt(int x) {

        if (x == 0 || x == 1) {
            return x;
        }

        int left = 0, right = 65536, i = (left + right) / 2, k = x / i;

        while (!(i == k + 1 || i == k)) {
            if (i > k) {
                right = i;
            } else {
                left = i;
            }
            i = (left + right) / 2;
            k = x / i;
        }

        return k;
    }
    public static int climbStairs(int n) {

        if (n == 1 || n == 2) {
            return n;
        }

        int[] stairs = new int[n];

        stairs[0] = 1;
        stairs[1] = 2;

        for (int i = 2; i < n; i++) {
            stairs[i] = stairs[i - 1] + stairs[i - 2];
        }

        return stairs[n - 1];
    }
    public static List<String> fullJustify(String[] words, int maxWidth) {

        int residue = maxWidth, space = 1, extra = 0, n;
        StringBuilder row = new StringBuilder();
        List<String> rowList = new ArrayList<>();
        List<String> list = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            if (words[i].length() <= residue) {
                rowList.add(words[i]);
                residue -= (words[i].length() + 1);
            } else {
                n = rowList.size();
                residue++;
                if (n != 1) {
                    space = residue / (n - 1) + 1;
                    extra = residue % (n - 1);
                }
                for (int k = 0; k < n; k++) {
                    row.append(rowList.get(k));
                    if (k == n - 1) {
                        break;
                    }
                    for (int j = 0; j < space; j++) {
                        row.append(' ');
                    }
                    if (extra-- > 0) {
                        row.append(' ');
                    }
                }
                if (n == 1) {
                    while (residue-- > 0) {
                        row.append(' ');
                    }
                }
                residue = maxWidth - words[i].length() - 1;
                list.add(row.toString());
                row.delete(0, maxWidth);
                rowList.clear();
                rowList.add(words[i]);
            }
        }

        for (int k = 0; k < rowList.size(); k++) {
            row.append(rowList.get(k)).append(' ');
        }

        if (residue == -1) {
            row.deleteCharAt(row.length() - 1);
        } else {
            for (int i = 0; i < residue; i++) {
                row.append(' ');
            }
        }

        list.add(row.toString());

        return list;
    }
    public static String simplifyPath(String path) {

        path += "/";

        List<String> list = new ArrayList<>();
        int n = path.length(), i = 0, length = 0;
        String name, ans = "";

        while (i < n) {
            while (i < n && path.charAt(i) == '/') {
                if (length > 0) {
                    name = path.substring(i - length, i);
                    if (name.equals(".") ) {
                        length = 0;
                    } else if (name.equals("..")) {
                        length = 0;
                        if (list.size() > 0) {
                            list.remove(list.size() - 1);
                        }
                    } else {
                        length = 0;
                        list.add(name);
                    }
                }
                i++;
            }
            length++;
            i++;
        }

        for (int k = 0; k < list.size(); k++) {
            ans += "/" + list.get(k);
        }

        return ans.length() == 0 ? "/" : ans;
    }

    public static void setZeroes(int[][] matrix) {

        boolean flag = false;

        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                flag = true;
                break;
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                matrix[0][0] = 0;
                break;
            }
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (matrix[0][0] == 0) {
            for (int i = 1; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }

        if (flag) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }

    }

    public static boolean searchMatrix(int[][] matrix, int target) {

        int n = matrix.length, m = matrix[0].length, index = 1;

        if (matrix[0][0] > target || matrix[n - 1][m - 1] < target) {
            return false;
        }

        while (index < n) {
            if (matrix[index][0] == target) {
                return true;
            } else if (matrix[index][0] < target) {
                index++;
            } else {
                break;
            }
        }

        index--;

        for (int j = 0; j < m; j++) {
            if (matrix[index][j] == target) {
                return true;
            } else if (matrix[index][j] > target) {
                return false;
            }
        }

        return false;
    }
    public static void sortColors(int[] nums) {

        int leftIndex = 0, n = nums.length, count = 0;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                nums[leftIndex++] = 0;
            } else if (nums[i] == 1) {
                count++;
            }
        }

        count += leftIndex;

        for (int i = leftIndex; i < count; i++) {
            nums[i] = 1;
        }

        for (int i = count; i < n; i++) {
            nums[i] = 2;
        }
    }

    public static List<List<Integer>> combine(int n, int k) {

        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        combine(1, n, k, list, lists);

        return lists;
    }

    public static void combine(int start, int end, int k, List<Integer> list, List<List<Integer>> lists) {

        if (k == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i <= end; i++) {
            list.add(i);
            combine(i + 1, end, k - 1, list, lists);
            list.remove(list.size() - 1);
        }
    }

    public static List<List<Integer>> subsets(int[] nums) {

        subsets(0, nums);

        return list;
    }

    public static void subsets(int index, int[] nums) {

        if (index == nums.length) {
            list.add(new ArrayList<>(newList));
            return;
        }

        newList.add(nums[index]);
        index++;
        subsets(index, nums);
        newList.remove(newList.size() - 1);
        subsets(index, nums);

    }

    public static boolean exist(char[][] board, String word) {

        byte[] bytes = word.getBytes();
        boolean[][] isUsed = new boolean[board.length][board[0].length];
        int index = 1;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == bytes[0] && exist(board, isUsed, i, j, bytes, index)) {
                    return true;
                }
            }
        }

        return false;
    }

    public static boolean exist(char[][] board, boolean[][] isUsed, int i, int j, byte[] bytes, int index) {

        boolean ans = false;

        if (index == bytes.length) {
            return true;
        }

        isUsed[i][j] = true;

        if (i < board.length - 1 && !isUsed[i + 1][j] && board[i + 1][j] == bytes[index]) {
            ans = ans || exist(board, isUsed, i + 1, j, bytes, index + 1);
        }

        if (j < board[0].length - 1 && !isUsed[i][j + 1] && board[i][j + 1] == bytes[index]) {
            ans = ans || exist(board, isUsed, i, j + 1, bytes, index + 1);
        }

        if (i > 0 && !isUsed[i - 1][j] && board[i - 1][j] == bytes[index]) {
            ans = ans || exist(board, isUsed, i - 1, j, bytes, index + 1);
        }

        if (j > 0 && !isUsed[i][j - 1] && board[i][j - 1] == bytes[index]) {
            ans = ans || exist(board, isUsed, i, j - 1, bytes, index + 1);
        }

        isUsed[i][j] = false;

        return ans;
    }

    public static int removeDuplicates(int[] nums) {

        int length = 2;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] == nums[length - 2]) {
                continue;
            }
            nums[length++] = nums[i];
        }

        return Math.min(nums.length, length);
    }

    public static String minWindow(String s, String t) {

        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) {
            return "";
        }

        // ascii('z') = 122
        int[] winFreq = new int[128];
        int[] tFreq = new int[128];
        char[] charArrayS = s.toCharArray();
        for (char c : t.toCharArray()) {
            tFreq[c]++;  // t中存在重复字符
        }

        int begin = 0;
        int minLen = sLen + 1;
        int distance = tLen;

        int left = 0;
        int right = 0;
        // [left, right)
        while (right < sLen) {
            char charRight = charArrayS[right++];
            // 非目标字符
            if (tFreq[charRight] == 0) {
                continue;
            }
            // 计算滑动窗口字符频数
            winFreq[charRight]++;
            // 超过tFreq字符频数, distance不再更新
            if (winFreq[charRight] <= tFreq[charRight]) {
                distance--;
            }

            while (distance == 0) {
                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }

                char charLeft = charArrayS[left++];
                if (tFreq[charLeft] == 0) {
                    continue;
                }

                winFreq[charLeft]--;
                if (winFreq[charLeft] < tFreq[charLeft]) {
                    distance++;
                }
            }
        }
        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }
    public static boolean search(int[] nums, int target) {

        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }

    public static ListNode deleteDuplicates(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode t = new ListNode(), p = head, ans = t;
        int value = p.val, count = 0;

        while (p.next != null) {
            if (value != p.next.val) {
                if (count == 0) {
                    t.next = p;
                    t = t.next;
                } else {
                    count = 0;
                }
                value = p.next.val;
            } else {
                count++;
            }
            p = p.next;
        }

        if (count == 0) {
            t.next = p;
        } else {
            t.next = null;
        }

        return ans.next;
    }

//    public static ListNode deleteDuplicates(ListNode head) {
//
//        if (head == null) {
//            return null;
//        }
//
//        ListNode p = head;
//
//        while (p.next != null) {
//            if (p.val == p.next.val) {
//                p.next = p.next.next;
//            } else {
//                p = p.next;
//            }
//        }
//
//        return head;
//    }

    public static int largestRectangleArea(int[] heights) {

        int n = heights.length, max = 0;
        int[] left = new int[n], right = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        Arrays.fill(right, n);
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                right[stack.peek()] = i;
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            max = Math.max(max, (right[i] - left[i] - 1) * heights[i]);
        }

        return max;
    }

    public static int maximalRectangle(char[][] matrix) {

        int row = matrix.length, column = matrix[0].length, max = 0;
        int[][] count = new int[row][column];

        for (int j = 0; j < column; j++) {
            if (matrix[0][j] == '1') {
                count[0][j] = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (matrix[i][j] == '1') {
                    count[i][j] = count[i - 1][j] + 1;
                }
            }
        }

        for (int i = 0; i < row; i++) {
            max = Math.max(max, largestRectangleArea(count[i]));
        }

        return max;
    }

    public static ListNode partition(ListNode head, int x) {

        ListNode left = new ListNode(), right = new ListNode(), p = head, l = left, r = right;

        while (p != null) {
            if (p.val < x) {
                l.next = p;
                l = l.next;
            } else {
                r.next = p;
                r = r.next;
            }
            p = p.next;
        }

        l.next = right.next;
        r.next = null;

        return left.next;
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {

        int[] num = new int[m];
        int left = 0, right = 0, index = 0;

        System.arraycopy(nums1, 0, num, 0, m);

        while (left < m && right < n) {
            if (num[left] > nums2[right]) {
                nums1[index] = nums2[right];
                right++;
            } else {
                nums1[index] = num[left];
                left++;
            }
            index++;
        }

        while (left < m) {
            nums1[index++] = num[left++];
        }

        while (right < n) {
            nums1[index++] = nums2[right++];
        }
    }

    public static List<Integer> grayCode(int n) {

        List<Integer> list = new ArrayList<>();
        int index, pow = 1;

        list.add(0);
        list.add(1);

        for (int i = 1; i < n; i++) {
            pow = pow << 1;
            index = pow;
            while (index > 0) {
                list.add(pow + list.get(--index));
            }
        }

        return list;
    }

    public static List<List<Integer>> subsetsWithDup(int[] nums) {

        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        Arrays.sort(nums);
        subsetsWithDup(lists, list, 0, nums);

        return lists;
    }

    public static void subsetsWithDup(List<List<Integer>> lists, List<Integer> list, int index, int[] nums) {

        if (index == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }

        list.add(nums[index]);
        subsetsWithDup(lists, list, index + 1, nums);
        list.remove(list.size() - 1);

        while (index + 1 < nums.length && nums[index] == nums[index + 1]) {
            index++;
        }
        subsetsWithDup(lists, list, index + 1, nums);

    }

    public static boolean isScramble(String s1, String s2) {


        return false;
    }

    public static void combine() {

        int[] f = new int[101];

        f[1] = 1;
        f[2] = 2;
        System.out.printf("0, 1, 2, ");

        for (int i = 3; i < 46; i++) {
            f[i] = f[i - 1] + f[i - 2];
            System.out.printf(f[i] + ", ");
        }
    }

    public static int numDecodings(String s) {

        int[] f = new int[]{0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};
        int count = 0, i = 0, ans = 1;
        byte[] bytes = s.getBytes();

        while (i < s.length()) {
            if (bytes[i] == '0' && (i == 0 || (bytes[i - 1] != '1' && bytes[i - 1] != '2'))) {
                return 0;
            }
            if (bytes[i] > '2') {
                i++;
                continue;
            }
            while (i < s.length() && (bytes[i] == '1' || bytes[i] == '2')) {
                i++;
                count++;
            }
            if (i == s.length()) {
                ans *= f[count];
            } else {
                if (bytes[i] == '0') {
                    ans *= f[count - 1];
                } else if (bytes[i] > '6' && bytes[i - 1] == '2') {
                    ans *= f[count];
                } else {
                    ans *= (f[count] + f[count - 1]);
                }
            }
            count = 0;
            i++;
        }

        return ans;
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {

        if (left == right) {
            return head;
        }

        ListNode newHead = new ListNode(-1, head), p = newHead, p1;
        ListNode[] nodes = new ListNode[right - left + 1];

        for (int i = 1; i < left; i++) {
            p = p.next;
        }

        p1 = p;
        p = p.next;

        for (int i = 0; i < right - left + 1; i++) {
            nodes[i] = p;
            p = p.next;
        }

        for (int i = right - left; i > -1; i--) {
            p1.next = nodes[i];
            p1 = p1.next;
        }

        p1.next = p;

        return newHead.next;
    }

    //        记录可能次数
    private static int count = 0;
    private static List<String> stringList = new ArrayList<>();
    private static List<Integer> intList = new ArrayList<>();

    public static int unName(String ip) {

        circle(0, 0, ip);
        System.out.println(stringList);
        return count;
    }

    public static void circle(int index, int num, String ip) {

        if (num == 4 && index == ip.length()) {
            count++;
            byte[] bytes = ip.getBytes();
            byte[] newBytes = new byte[bytes.length + 3];
            for (int i = 0; i < 3; i++) {
                newBytes[i + intList.get(i)] = '.';
            }
            int index1 = 0, index2 = 0;
            while (index1 < bytes.length) {
                if (newBytes[index2] == '.') {
                    index2++;
                }
                newBytes[index2++] = bytes[index1++];
            }
            stringList.add(new String(newBytes));
        }

        if (num == 4 || index == ip.length()) {
            return;
        }

        intList.add(index + 1);
        circle(index + 1, num + 1, ip);
        intList.remove(intList.size() - 1);

        if (ip.charAt(index) != '0' && index < ip.length() - 1) {
            intList.add(index + 2);
            circle(index + 2, num + 1, ip);
            intList.remove(intList.size() - 1);
            if (index < ip.length() - 2 && Integer.valueOf(ip.substring(index, index + 3)) < 256) {
                intList.add(index + 3);
                circle(index + 3, num + 1, ip);
                intList.remove(intList.size() - 1);
            }
        }
    }

    public static List<Integer> inorderTraversal(TreeNode root) {

        if (root == null) {
            return intList;
        }

        inorderTraversal(root.left);
        intList.add(root.val);
        inorderTraversal(root.right);

        return intList;
    }



}

//class ListNode implements Serializable {
//
//    int val;
//    ListNode next;
//
//    public ListNode() {
//    }
//
//    public ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//
//    public ListNode(int val) {
//        this.val = val;
//    }
//
//    @Override
//    public String toString() {
//        return "ListNode{" +
//                "val=" + val +
//                ", next=" + next +
//                '}';
//    }
//}

class FinalDemo {

    public final double id = Math.random();
    public static double user = Math.random();


}

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}